#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

//暴力解法
class Solution
{
public:
    string longestPalindrome(string s)
    {
        int len = s.length();
        int max_length = 0;
        string str_re;
        for (int i = 0; i < len; i++)
        {
            for (int j = 1; j < len; j++)
            {
                string str = s.substr(i, j + 1 - i);

                string strr = str;
                reverse(strr.begin(), strr.end());

                if (str.compare(strr) == 0 && max_length < strr.length())
                {
                    max_length = strr.length();
                    str_re = str;
                }
            }
        }
        return str_re;
    }
};

//中心扩散法
class Solution2
{
public:
    int max = 0;
    string ret = "";
    void spread(string &s, int left, int right)
    {
        int L = left, R = right;
        while (L >= 0 && R < s.size() && s[L] == s[R])
        { //向左向右扩散
            if (R - L + 1 > max)
            {
                max = R - L + 1;
                ret = s.substr(L, R - L + 1);
            }
            L--;
            R++;
        }
    }
    string longestPalindrome(string s)
    {
        if (s.size() <= 1)
            return s;
        for (int i = 0; i < s.size(); i++)
        {
            spread(s, i, i);     //从单个字符开始扩散
            spread(s, i, i + 1); //从相邻的两个字符开始扩散
        }
        return ret;
    }
};
